package Hot100.leetcode.editor.cn.code.数组;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

//Java：合并区间
public class MergeIntervals{
    public static void main(String[] args) {
        Solution solution = new MergeIntervals().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals,(p,q) -> p[0] - q[0]);//首先得按照左端点排序后续才好判断更新右端点
        //在合并区间的过程中，我们无法预先知道最终会剩下多少个区间。
        // 使用List可以动态地添加或合并区间，而不需要预先确定数组大小。
        List<int[]> ans = new ArrayList<>();
        for (int[] p : intervals) {
            int m = ans.size();//注意集合的下标也是0开始的，而且这题一个数组就两个元素
            if (m > 0 && p[0] <= ans.get(m - 1)[1]){//刚开始size为0进不来
                ans.get(m-1)[1] = Math.max(ans.get(m-1)[1], p[1]);//更新右端点的最大值
            }else {//不相交无法合并
                ans.add(p);
            }
        }
        return ans.toArray(new int[ans.size()][]);
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}